package cn.com.yang.datastruct.heap;

import java.util.Arrays;

/**
 * 数组堆排序
 * TODO
 * @author yangyijin
 * @since 2024年2月5日-下午8:13:11
 */
public class HeapSort {
	public static void main(String[] args) {
		int[] arr = new int[] {1,45,3,22,39,98,12};
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}
	//堆排序的实现方法
	public static void sort(int[] arr) {
		//1.首先把无序数组调整为堆
		//找到最后一个非叶子节点 数组长度/2-1
		for(int i=arr.length/2-1;i>=0;i--) {
			//具体的调整，封装成一个方法，因为反复调用
			adjustHeap(arr,i,arr.length);
		}
		//2.和3一起实现
		for(int j=arr.length-1;j>0;j--) {
			//交换堆顶和堆尾位置
			swap(arr,0,j);
			//交换完后，剩下的立马调整为堆
			adjustHeap(arr, 0, j);
		}
	}
	/**
	 * 交换堆顶和堆低
	 * @param arr
	 * @param i
	 * @param j
	 */
	private static void swap(int[] arr, int i, int j) {
		// TODO Auto-generated method stub
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	/**
	 * 调整堆
	 * @param arr 数组
	 * @param i 被调整的节点下标
	 * @param j 数组长度
	 */
	private static void adjustHeap(int[] arr, int i, int j) {
		int temp = arr[i];//临时存起来
		for(int k =i*2+1;k<j;k=k*2+1) {
			if(k+1<j && arr[k]<arr[k+1]) {//说明右子节点大,实际上找最大的子节点
				k++;
			}
			if(temp>=arr[k]) {
				break;
			}else{
				//把大的值拉上去
				arr[i]=arr[k];
				i=k;
			}
		}
		arr[i]=temp;//被调整的位置
	}
}
